package org.usmile.algorithms.learn.graph.dfs;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SingleSourcePath {
    /**
     * 深度优先遍历 递归
     */
    public List<Integer> hasSource(Graph graph, int source, int target) {
        if (graph == null) {
            return new ArrayList<>();
        }

        int[] prevs = new int[graph.getV()];
        Arrays.fill(prevs, -1);
        boolean[] visited = new boolean[graph.getV()];
        dfs(graph, source, visited, source, prevs);
        if (!visited[target]) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();

        while (target != source) {
            result.add(target);
            target = prevs[target];
        }
        result.add(source);

        Collections.reverse(result);


        return result;
}

    private void dfs(Graph graph, int v, boolean[] visited, int prev, int[] prevs) {
        visited[v] = true;
        prevs[v] = prev;

        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                dfs(graph, w, visited, v, prevs);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new AdjList(8);
        graph.addEdge(4, 2);
        graph.addEdge(0, 1);
        graph.addEdge(5, 6);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);

        System.out.println(new SingleSourcePath().hasSource(graph, 0 , 3));
    }
}
